package robotlion.pathfinding;

import java.awt.Point;
import java.util.ArrayList;
import javax.swing.tree.*;
import robotlion.model.Carte;

/**
 *
 * @author test
 */
public class PathfindingDijkstra {

    private Carte carte;
    private DefaultTreeModel arbre;
    private ArrayList<DefaultMutableTreeNode> listeFeuilles;
    private int poidsCumule; // Poids du dernier dijkstra lancé
    

    public PathfindingDijkstra(Carte carte) {
        this.carte = carte;
        
        DefaultMutableTreeNode racine = new DefaultMutableTreeNode();
        this.arbre = new DefaultTreeModel(racine);
        
        this.listeFeuilles = new ArrayList<>();
        
        this.poidsCumule = 0;
    }
    
    // Pour un point donné et une destination, retourne le point le plus proche 
    // en termes de poids
    // On passe une deuxième coordonnée, permettant de connaitre le niveau
    // d'accessibilité du robot, afin de ne pas examiner des cases
    // inaccessibles par le robot
    public DefaultMutableTreeNode pointLePlusProche(DefaultMutableTreeNode dOuJeViens, int niveauAccessibilite, Point objectif)
    {
        int plusPetitPoids = Integer.MAX_VALUE; // Valeur "infinie"
        // Récupération de la coordonnée de départ
        Point depart = (Point)dOuJeViens.getUserObject();
        Point courant = (Point)depart.clone();
        Point pointPlusPetit = (Point)depart.clone();
        DefaultMutableTreeNode noeudPlusPetit = dOuJeViens;
        
        double distancePlusPetite = Math.sqrt(Math.pow((courant.x - objectif.x),2)
                                             +Math.pow((courant.y - objectif.y),2));
        
        // Toutes les cases sur lesquelles on peut se déplacer à partir de la
        // case de départ
        Point casesAlentour [] = {new Point (courant.x, courant.y+1),
                                  new Point (courant.x, courant.y-1),
                                  new Point (courant.x-1, courant.y),
                                  new Point (courant.x+1, courant.y)};
        
        // Récupération du parent (la case où on était à l'itération précédente)
        DefaultMutableTreeNode parent = (DefaultMutableTreeNode)dOuJeViens.getParent();
        Point coordonneeParent;
        boolean estExplore = false;
        
        Object[] lesObjets = null;
        
        if (parent != null)
        {
            coordonneeParent = (Point) parent.getUserObject();
            System.out.println("Parent : ("+ coordonneeParent.getX()+"; "+coordonneeParent.getY()+")");
            
            // On parcourt l'ensemble du chemin courant
            // en essayant de retrouver si uneCase a déja
            // été explorée            
            lesObjets = parent.getUserObjectPath();
        }
        else
        {
            coordonneeParent = new Point();
        };
        
        // Pour chaque case alentour
        for (Point uneCase : casesAlentour)
        {           
            int i = 0; estExplore = false;
            
            if (lesObjets != null)
            {
                while (i < lesObjets.length && !lesObjets[i].equals((Object) uneCase))
                {
                    i++;
                }

                // Si i < lesObjets.length, cela signifie que le chemin a déja été exploré
                if (i < lesObjets.length)
                {
                    Point p = (Point) lesObjets[i];
                    estExplore = true;
                }
            }
            
            //if (parent == null || !uneCase.equals(coordonneeParent))
            if (parent == null || !estExplore)
            {
                try
                {
                    courant.x = uneCase.x;
                    courant.y = uneCase.y;

                    // Si le point n'est pas en dehors de la carte
                    // et qu'il est accessible pour le robot
                    if (carte.getAccessibilite(courant) < Integer.MAX_VALUE
                            && carte.getAccessibilite(courant) < niveauAccessibilite)
                    {
                        
                        // On ajoute le noeud à l'arbre des chemins explorés, en 
                        // tant qu'enfant du noeud représentant le point de départ
                        DefaultMutableTreeNode node = new DefaultMutableTreeNode(courant.clone());
                        dOuJeViens.add(node);

                        // Retrait du noeud de la liste des feuilles, vu que l'on 
                        // vient d'y ajouter un enfant, et ajout de l'enfant en question
                        // dans cette liste
                        if (this.listeFeuilles.contains(dOuJeViens))
                        {
                            this.listeFeuilles.remove(dOuJeViens);
                        }

                        // Ajout de l'enfant à la liste des feuilles
                        this.listeFeuilles.add(node);
                        
                        // Savant calcul
                        // Pour "orienter" l'algorithme, c'est à dire lui donner
                        // une direction à suivre si tous les points adjacents
                        // se valent, on décide de suivre la démarche suivante :
                        // On calcule la valeur absolue de courant.X - objectif.X,
                        // et on choisit le point dont cette valeur est la plus petite
                        // Si deux de ces valeurs sont identiques, on fait de même
                        // avec courant.Y - objectif.Y
                        // Cela permet de ne pas choisir une direction arbitraire
                        // SI PLUSIEURS POINTS ADJACENTS ONT LE MEME POIDS !!!
                        double distance = Math.sqrt(Math.pow((courant.x - objectif.x),2)
                                                    +Math.pow((courant.y - objectif.y),2));

                        if (carte.getAccessibilite(courant) < plusPetitPoids ||
                                (carte.getAccessibilite(courant) == plusPetitPoids
                                && distance < distancePlusPetite))
                        {
                            plusPetitPoids = carte.getAccessibilite(courant);
                            pointPlusPetit = (Point)courant.clone();
                            noeudPlusPetit = node;
                            
                            distancePlusPetite = distance;
                        } 
                    }
                }
                catch (Exception e) {}

            }
        }
  
        System.out.println("Le plus petit : ("+pointPlusPetit.getX()+"; "+pointPlusPetit.getY()+") - Poids : "+plusPetitPoids);
        
        // Si on a bien trouvé un point proche
        if (plusPetitPoids < Integer.MAX_VALUE)
        {
            return noeudPlusPetit; 
        }
        
        // Sinon, c'est que l'on est bloqué, l'appelant devra donc utiliser
        // cette valeur de retour pour savoir qu'il doit revenir en arrière
        return null;
    }
    
    // Algorithme de Dijkstra
    // Nécessite en entrée :
    // - un objet de la classe DefaultMutableTreeNode contenant
    // la coordonnée de départ
    // - La coordonnée d'arrivée
    // - Le poids maximum : représente un niveau d'accessibilité, c'est à dire
    // que toutes les cases dont le poids est > à cette valeur ne seront pas accessibles
    // Les autres paramètres doivent être positionnés respectivement à 0 et true
    // (paramètres utilisés pour la récursivité)
    public DefaultMutableTreeNode dijkstra(DefaultMutableTreeNode depart, Point arrivee, int poidsMaximum, int poids, boolean premierPassage)
    {
        try
        {
            // Si le point demandé n'est pas accessible par le robot,
            // alors depart.getUserObject() sera null, on décide donc
            // de terminer l'algorithme en retournant null à l'appelant,
            // afin de lui indiquer que le robot ne peut pas atteindre l'objectif*
            if (depart == null)
            {
                System.out.println("Echec de l'algorithme");
                this.poidsCumule = Integer.MAX_VALUE;
                return null;
            }
            
            Point coordDepart = (Point) depart.getUserObject();
            
            if (premierPassage == true)
            {
                poids = this.carte.getAccessibilite(coordDepart);
                
                this.arbre.setRoot(depart);
            }
            
            System.out.println("Départ : ("+coordDepart.getX()+"; "
                    +coordDepart.getY()+")");
            
            if (coordDepart.equals(arrivee))
            {
                recupererPlusCourtChemin(depart);
                this.poidsCumule = poids;
                return depart;
            }
            
            // On met de côté le point le plus accessible
            DefaultMutableTreeNode noeudProche = this.pointLePlusProche(depart, poidsMaximum, arrivee);
            
            Point proche = null;
            
            // Le poids cumulé est mis à une valeur "infinie"
            // La plupart du temps, il sera remis à jour dans les lignes suivantes,
            // mais si noeudProche == null, alors cette valeur infinie permettra
            // d'indiquer à l'application que ce chemin n'est pas praticable
            int poidsCumule = Integer.MAX_VALUE;
            double distanceCumulee = 0.1;
            
            if (noeudProche != null)
            {
                proche = (Point) noeudProche.getUserObject();            
                poidsCumule = poids + this.carte.getAccessibilite(proche) + 1;
                
                distanceCumulee = Math.sqrt(Math.pow((proche.x - arrivee.x),2)
                                                    +Math.pow((proche.y - arrivee.y),2));
            }
            else
            {
                this.listeFeuilles.remove(depart);
            }
            
            // On vérifie maintenant que ce point soit toujours le plus "petit" 
            // en terme de poids, par rapport à tous les autres points explorés
            // On ne doit donc examiner que les feuilles de l'arbre
            
            System.out.println("Nb de feuilles : "+this.listeFeuilles.size());
            
            System.out.println("\\\\\\");
            
            int somme;
            
            for (DefaultMutableTreeNode node : this.listeFeuilles)
            {
                somme = 0;
                
                // On remonte la hiérarchie de ce noeud, 
                // afin de calculer le poids cumulé de celui-ci
                for (Object o : node.getUserObjectPath())
                {
                    Point c = (Point) o;
                    
                    // Somme des poids de la liste
                    somme += this.carte.getAccessibilite(c); 
                }
                
                Point p = (Point)node.getUserObject();
                
                //System.out.print("\n");
                double sommeDistance = Math.sqrt(Math.pow((p.x - arrivee.x),2)
                                          +Math.pow((p.y - arrivee.y),2));
                
                //if (somme < poidsCumule)
                if ((somme+sommeDistance*2) < (poidsCumule+distanceCumulee*2))
                {
                    System.out.println("Somme : "+ (somme+sommeDistance*2));
                    System.out.println("Poids Cumulé  : "+(poidsCumule+distanceCumulee*2));
                    
                    proche = (Point)node.getUserObject();
                    poidsCumule = somme;
                    
                    System.out.println("Nouveau plus petit trouvé : ("+proche.getX()+"; "
                    +proche.getY()+")");
                    
                    // Et on indique à l'application que le nouveau noeud
                    // de plus petit poids est "node"
                    noeudProche = node;
                }
            }
            
            // Et on rappelle la méthode sur ce point en mettant à jour le poids
            return dijkstra(noeudProche, arrivee, poidsMaximum, poidsCumule, false);
        }
        catch (StackOverflowError s)
        {
            System.out.println("Echec de l'algorithme");
            this.poidsCumule = Integer.MAX_VALUE;
            s.printStackTrace();
            return null;
        }
        catch (Exception e)
        {
            e.printStackTrace();
            return null;
        }
    }
    
    // Simple affichage du chemin
    // Retourne également un tableau composé de tous les points composants
    // le chemin idéal
    public ArrayList recupererPlusCourtChemin(DefaultMutableTreeNode noeudFinal)
    {
        int i = 1;
        
        ArrayList<Point> meilleurChemin = new ArrayList<>();
        
        for (Object o : noeudFinal.getUserObjectPath())
        {
            Point uneCoordonnee = (Point) o;
            meilleurChemin.add(uneCoordonnee);
            System.out.println("Etape "+i+" - ("+uneCoordonnee.getX()+"; "
                    +uneCoordonnee.getY()+")");
            
            i++;
        }
        
        return meilleurChemin;
    }
    
    // Retourne le poids cumulé du dernier algorithme de dijkstra utilisé
    public int getLastPoidsCumule()
    {
        return this.poidsCumule;
    }
}
